Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

給一個 array 紀錄每日天氣，如果明天的天氣大於今天的天氣則紀錄 1，如果第四天的天氣才大於今天的天氣則紀錄 3 (要經過 3 天才會變得比今天暖)。

Double For-Loop

最簡單的解法可以用兩個 for-loop 去遍歷陣列，當 r > l 的時候將 r - l 的值放入 res

var dailyTemperatures = function(temperatures) {
    const res = [];
    for (let l = 0; l < temperatures.length; l++) {
        let r = l + 1;
        while (temperatures[r] <= temperatures[l] && r < temperatures.length) {
           r++;
        }
        if (r < temperatures.length) res.push(r - l);
        else res.push(0);
    }
    return res;
};

雖然這樣有辦法解但他的 Time complexity 是 O(n^2)，再來找找有沒有更好的方法。

Monotonic Stack

所謂的 Monotonic Stack 就是利用 stack 維護單純遞增或單純遞減的資料，用來找出下一個更大(或更小)的值，以這個題目為例 temperatures = [73,74,75,71,69,72,76,73]

從最後一項開始，因為 stack 為空的所以將 73 和他的 index 放入 stack 中，而因為是第一個所以 res 放入 0 代表沒有比她更大的值。

移動 i 到 76 並將他和 stack 中最上面的值 (73) 比較，如果比較大則將 stack 中的值 pop 出來直到遇到比 76 大的值或 stack 清空。

這邊將 73 pop 出來後 stack 清空了所以將 76 和他的 index 放入 stack 中，而因為是第一個所以 res 放入 0 代表沒有比她更大的值。

移動 i 到 72 將他和 stack 中最上面的值 (76) 比較，72 比較小所以直接將它放入 stack 中並將他的 index 和 76 的 index 相減放入 res 中

移動 i 到 69 將他和 stack 中最上面的值 (72) 比較，69 比較小所以直接將它放入 stack 中並將他的 index 和 72 的 index 相減放入 res 中

移動 i 到 71 將他和 stack 中最上面的值 (69) 比較，將 stack 中的值 pop 出來直到遇到比 71 大的值或 stack 清空

這邊將 69 pop 出去後 72 大於 71 於是停止 pop 並將 71 和他的 index 放入 stack 中，res 則放入 72 的 index 減去 71 的 index

諸如此類，移動 i 的時候將 i 的值與 stack 中最上面的值做比對，如果 stack 中的值小於 i 的值，則將 stack 的值 pop 出來直到大於 i 或是 stack 清空。

Coding

var dailyTemperatures = function(temperatures) {
    const stack = [], res = [];
    for (let i = temperatures.length - 1; i >= 0; i--) {
        if (stack.length === 0) {
            stack.push({ val: temperatures[i], index: i });
            res[i] = 0;
            continue;
        }

        if (stack[stack.length - 1].val > temperatures[i]) {
            res[i] = stack[stack.length - 1].index - i;
            stack.push({ val: temperatures[i], index: i });
        } else {
            while (stack[stack.length - 1]?.val <= temperatures[i]) {
                stack.pop();
            }
            if (stack.length === 0) {
                stack.push({ val: temperatures[i], index: i });
                res[i] = 0;
                continue;
            }
            res[i] = stack[stack.length - 1].index - i;
            stack.push({ val: temperatures[i], index: i });
        }
    }
    return res;
};

Time complexity: O(n)

Reference

• Monotonic Stack Data Structure Explained